/**
 * https://leetcode.cn/problems/minimum-time-to-collect-all-apples-in-a-tree/submissions/582741419/
 * 1443.收集树上所有苹果的最少时间 1683
 * medium 陈贝纯 2024.11.24
 * dfs
 */

class Solution {
public:
    int dfs(int v,vector<vector<int>>& parent,vector<bool>& hasApple,vector<bool>& vist){
        vist[v]=false;
        int time=0;
        for(auto a:parent[v]){
            if(vist[a]){
                time+=dfs(a,parent,hasApple,vist);
            }
        }
        if(v!=0&&(hasApple[v]||time>0))
        time+=2;
        return time;
    }
    int minTime(int n, vector<vector<int>>& edges, vector<bool>& hasApple) {
        vector<vector<int>> parent(n);
        for(auto edge:edges){
            parent[edge[0]].push_back(edge[1]);
            parent[edge[1]].push_back(edge[0]);
        }
        vector<bool> vist(n,true);
        return dfs(0,parent,hasApple,vist);
    }
};